home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / String.cc < prev    next >
C/C++ Source or Header  |  1994-10-12  |  28KB  |  1,301 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   String class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <String.h>
  26. #include <std.h>
  27. #include <ctype.h>
  28. #include <limits.h>
  29. #include <new.h>
  30. #include <builtin.h>
  31.  
  32. void String::error(const char* msg) const
  33. {
  34.   (*lib_error_handler)("String", msg);
  35. }
  36.  
  37. String::operator const char*() const
  38. { 
  39.   return (const char*)chars();
  40. }
  41.  
  42. //  globals
  43.  
  44. StrRep  _nilStrRep = { 0, 1, { 0 } }; // nil strings point here
  45. String _nilString;               // nil SubStrings point here
  46.  
  47.  
  48.  
  49.  
  50. /*
  51.  the following inline fcts are specially designed to work
  52.  in support of String classes, and are not meant as generic replacements
  53.  for libc "str" functions.
  54.  
  55.  inline copy fcts -  I like left-to-right from->to arguments.
  56.  all versions assume that `to' argument is non-null
  57.  
  58.  These are worth doing inline, rather than through calls because,
  59.  via procedural integration, adjacent copy calls can be smushed
  60.  together by the optimizer.
  61. */
  62.  
  63. // copy n bytes
  64. inline static void ncopy(const char* from, char* to, int n)
  65. {
  66.   if (from != to) while (--n >= 0) *to++ = *from++;
  67. }
  68.  
  69. // copy n bytes, null-terminate
  70. inline static void ncopy0(const char* from, char* to, int n)
  71. {
  72.   if (from != to) 
  73.   {
  74.     while (--n >= 0) *to++ = *from++;
  75.     *to = 0;
  76.   }
  77.   else
  78.     to[n] = 0;
  79. }
  80.  
  81. // copy until null
  82. inline static void scopy(const char* from, char* to)
  83. {
  84.   if (from != 0) while((*to++ = *from++) != 0);
  85. }
  86.  
  87. // copy right-to-left
  88. inline static void revcopy(const char* from, char* to, short n)
  89. {
  90.   if (from != 0) while (--n >= 0) *to-- = *from--;
  91. }
  92.  
  93.  
  94. inline static int slen(const char* t) // inline  strlen
  95. {
  96.   if (t == 0)
  97.     return 0;
  98.   else
  99.   {
  100.     const char* a = t;
  101.     while (*a++ != 0);
  102.     return a - 1 - t;
  103.   }
  104. }
  105.  
  106. // minimum & maximum representable rep size
  107.  
  108. #define MAXStrRep_SIZE   ((1 << (sizeof(short) * CHAR_BIT - 1)) - 1)
  109. #define MINStrRep_SIZE   16
  110.  
  111. #ifndef MALLOC_MIN_OVERHEAD
  112. #define MALLOC_MIN_OVERHEAD  4
  113. #endif
  114.  
  115. // The basic allocation primitive:
  116. // Always round request to something close to a power of two.
  117. // This ensures a bit of padding, which often means that
  118. // concatenations don't have to realloc. Plus it tends to
  119. // be faster when lots of Strings are created and discarded,
  120. // since just about any version of malloc (op new()) will
  121. // be faster when it can reuse identically-sized chunks
  122.  
  123. inline static StrRep* Snew(int newsiz)
  124. {
  125.   unsigned int siz = sizeof(StrRep) + newsiz + MALLOC_MIN_OVERHEAD;
  126.   unsigned int allocsiz = MINStrRep_SIZE;
  127.   while (allocsiz < siz) allocsiz <<= 1;
  128.   allocsiz -= MALLOC_MIN_OVERHEAD;
  129.   if (allocsiz >= MAXStrRep_SIZE)
  130.     (*lib_error_handler)("String", "Requested length out of range");
  131.     
  132.   StrRep* rep = (StrRep *) new char[allocsiz];
  133.   rep->sz = allocsiz - sizeof(StrRep);
  134.   return rep;
  135. }
  136.  
  137. // Do-something-while-allocating routines.
  138.  
  139. // We live with two ways to signify empty Sreps: either the
  140. // null pointer (0) or a pointer to the nilStrRep.
  141.  
  142. // We always signify unknown source lengths (usually when fed a char*)
  143. // via len == -1, in which case it is computed.
  144.  
  145. // allocate, copying src if nonull
  146.  
  147. StrRep* Salloc(StrRep* old, const char* src, int srclen, int newlen)
  148. {
  149.   if (old == &_nilStrRep) old = 0;
  150.   if (srclen < 0) srclen = slen(src);
  151.   if (newlen < srclen) newlen = srclen;
  152.   StrRep* rep;
  153.   if (old == 0 || newlen > old->sz)
  154.     rep = Snew(newlen);
  155.   else
  156.     rep = old;
  157.  
  158.   rep->len = newlen;
  159.   ncopy0(src, rep->s, srclen);
  160.  
  161.   if (old != rep && old != 0) delete old;
  162.  
  163.   return rep;
  164. }
  165.  
  166. // reallocate: Given the initial allocation scheme, it will
  167. // generally be faster in the long run to get new space & copy
  168. // than to call realloc
  169.  
  170. static StrRep*
  171. Sresize(StrRep* old, int newlen)
  172. {
  173.   if (old == &_nilStrRep) old = 0;
  174.   StrRep* rep;
  175.   if (old == 0)
  176.     rep = Snew(newlen);
  177.   else if (newlen > old->sz)
  178.   {
  179.     rep = Snew(newlen);
  180.     ncopy0(old->s, rep->s, old->len);
  181.     delete old;
  182.   }
  183.   else
  184.     rep = old;
  185.  
  186.   rep->len = newlen;
  187.  
  188.   return rep;
  189. }
  190.  
  191. void
  192. String::alloc (int newsize)
  193. {
  194.   unsigned short old_len = rep->len;
  195.   rep = Sresize(rep, newsize);
  196.   rep->len = old_len;
  197. }
  198.  
  199. // like allocate, but we know that src is a StrRep
  200.  
  201. StrRep* Scopy(StrRep* old, const StrRep* s)
  202. {
  203.   if (old == &_nilStrRep) old = 0;
  204.   if (s == &_nilStrRep) s = 0;
  205.   if (old == s) 
  206.     return (old == 0)? &_nilStrRep : old;
  207.   else if (s == 0)
  208.   {
  209.     old->s[0] = 0;
  210.     old->len = 0;
  211.     return old;
  212.   }
  213.   else 
  214.   {
  215.     StrRep* rep;
  216.     int newlen = s->len;
  217.     if (old == 0 || newlen > old->sz)
  218.     {
  219.       if (old != 0) delete old;
  220.       rep = Snew(newlen);
  221.     }
  222.     else
  223.       rep = old;
  224.     rep->len = newlen;
  225.     ncopy0(s->s, rep->s, newlen);
  226.     return rep;
  227.   }
  228. }
  229.  
  230. // allocate & concatenate
  231.  
  232. StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen)
  233. {
  234.   if (old == &_nilStrRep) old = 0;
  235.   if (srclen < 0) srclen = slen(s);
  236.   if (tlen < 0) tlen = slen(t);
  237.   int newlen = srclen + tlen;
  238.   StrRep* rep;
  239.  
  240.   if (old == 0 || newlen > old->sz || 
  241.       (t >= old->s && t < &(old->s[old->len]))) // beware of aliasing
  242.     rep = Snew(newlen);
  243.   else
  244.     rep = old;
  245.  
  246.   rep->len = newlen;
  247.  
  248.   ncopy(s, rep->s, srclen);
  249.   ncopy0(t, &(rep->s[srclen]), tlen);
  250.  
  251.   if (old != rep && old != 0) delete old;
  252.  
  253.   return rep;
  254. }
  255.  
  256. // double-concatenate
  257.  
  258. StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen,
  259.              const char* u, int ulen)
  260. {
  261.   if (old == &_nilStrRep) old = 0;
  262.   if (srclen < 0) srclen = slen(s);
  263.   if (tlen < 0) tlen = slen(t);
  264.   if (ulen < 0) ulen = slen(u);
  265.   int newlen = srclen + tlen + ulen;
  266.   StrRep* rep;
  267.   if (old == 0 || newlen > old->sz || 
  268.       (t >= old->s && t < &(old->s[old->len])) ||
  269.       (u >= old->s && u < &(old->s[old->len])))
  270.     rep = Snew(newlen);
  271.   else
  272.     rep = old;
  273.  
  274.   rep->len = newlen;
  275.  
  276.   ncopy(s, rep->s, srclen);
  277.   ncopy(t, &(rep->s[srclen]), tlen);
  278.   ncopy0(u, &(rep->s[srclen+tlen]), ulen);
  279.  
  280.   if (old != rep && old != 0) delete old;
  281.  
  282.   return rep;
  283. }
  284.  
  285. // like cat, but we know that new stuff goes in the front of existing rep
  286.  
  287. StrRep* Sprepend(StrRep* old, const char* t, int tlen)
  288. {
  289.   char* s;
  290.   int srclen;
  291.   if (old == &_nilStrRep || old == 0)
  292.   {
  293.     s = 0; old = 0; srclen = 0;
  294.   }
  295.   else
  296.   {
  297.     s = old->s; srclen = old->len;
  298.   }
  299.   if (tlen < 0) tlen = slen(t);
  300.   int newlen = srclen + tlen;
  301.   StrRep* rep;
  302.   if (old == 0 || newlen > old->sz || 
  303.       (t >= old->s && t < &(old->s[old->len])))
  304.     rep = Snew(newlen);
  305.   else
  306.     rep = old;
  307.  
  308.   rep->len = newlen;
  309.  
  310.   revcopy(&(s[srclen]), &(rep->s[newlen]), srclen+1);
  311.   ncopy(t, rep->s, tlen);
  312.  
  313.   if (old != rep && old != 0) delete old;
  314.  
  315.   return rep;
  316. }
  317.  
  318.  
  319. // string compare: first argument is known to be non-null
  320.  
  321. inline static int scmp(const char* a, const char* b)
  322. {
  323.   if (b == 0)
  324.     return *a != 0;
  325.   else
  326.   {
  327.     signed char diff = 0;
  328.     while ((diff = *a - *b++) == 0 && *a++ != 0);
  329.     return diff;
  330.   }
  331. }
  332.  
  333.  
  334. inline static int ncmp(const char* a, int al, const char* b, int bl)
  335. {
  336.   int n = (al <= bl)? al : bl;
  337.   signed char diff;
  338.   while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  339.   return al - bl;
  340. }
  341.  
  342. int fcompare(const String& x, const String& y)
  343. {
  344.   const char* a = x.chars();
  345.   const char* b = y.chars();
  346.   int al = x.length();
  347.   int bl = y.length();
  348.   int n = (al <= bl)? al : bl;
  349.   signed char diff = 0;
  350.   while (n-- > 0)
  351.   {
  352.     char ac = *a++;
  353.     char bc = *b++;
  354.     if ((diff = ac - bc) != 0)
  355.     {
  356.       if (ac >= 'a' && ac <= 'z')
  357.         ac = ac - 'a' + 'A';
  358.       if (bc >= 'a' && bc <= 'z')
  359.         bc = bc - 'a' + 'A';
  360.       if ((diff = ac - bc) != 0)
  361.         return diff;
  362.     }
  363.   }
  364.   return al - bl;
  365. }
  366.  
  367. // these are not inline, but pull in the above inlines, so are 
  368. // pretty fast
  369.  
  370. int compare(const String& x, const char* b)
  371. {
  372.   return scmp(x.chars(), b);
  373. }
  374.  
  375. int compare(const String& x, const String& y)
  376. {
  377.   return scmp(x.chars(), y.chars());
  378. }
  379.  
  380. int compare(const String& x, const SubString& y)
  381. {
  382.   return ncmp(x.chars(), x.length(), y.chars(), y.length());
  383. }
  384.  
  385. int compare(const SubString& x, const String& y)
  386. {
  387.   return ncmp(x.chars(), x.length(), y.chars(), y.length());
  388. }
  389.  
  390. int compare(const SubString& x, const SubString& y)
  391. {
  392.   return ncmp(x.chars(), x.length(), y.chars(), y.length());
  393. }
  394.  
  395. int compare(const SubString& x, const char* b)
  396. {
  397.   if (b == 0)
  398.     return x.length();
  399.   else
  400.   {
  401.     const char* a = x.chars();
  402.     int n = x.length();
  403.     signed char diff;
  404.     while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  405.     return (*b == 0) ? 0 : -1;
  406.   }
  407. }
  408.  
  409. /*
  410.  index fcts
  411. */
  412.  
  413. int String::search(int start, int sl, char c) const
  414. {
  415.   const char* s = chars();
  416.   if (sl > 0)
  417.   {
  418.     if (start >= 0)
  419.     {
  420.       const char* a = &(s[start]);
  421.       const char* lasta = &(s[sl]);
  422.       while (a < lasta) if (*a++ == c) return --a - s;
  423.     }
  424.     else
  425.     {
  426.       const char* a = &(s[sl + start + 1]);
  427.       while (--a >= s) if (*a == c) return a - s;
  428.     }
  429.   }
  430.   return -1;
  431. }
  432.  
  433. int String::search(int start, int sl, const char* t, int tl) const
  434. {
  435.   const char* s = chars();
  436.   if (tl < 0) tl = slen(t);
  437.   if (sl > 0 && tl > 0)
  438.   {
  439.     if (start >= 0)
  440.     {
  441.       const char* lasts = &(s[sl - tl]);
  442.       const char* lastt = &(t[tl]);
  443.       const char* p = &(s[start]);
  444.  
  445.       while (p <= lasts)
  446.       {
  447.         const char* x = p++;
  448.         const char* y = t;
  449.         while (*x++ == *y++) if (y >= lastt) return --p - s;
  450.       }
  451.     }
  452.     else
  453.     {
  454.       const char* firsts = &(s[tl - 1]);
  455.       const char* lastt =  &(t[tl - 1]);
  456.       const char* p = &(s[sl + start + 1]); 
  457.  
  458.       while (--p >= firsts)
  459.       {
  460.         const char* x = p;
  461.         const char* y = lastt;
  462.         while (*x-- == *y--) if (y < t) return ++x - s;
  463.       }
  464.     }
  465.   }
  466.   return -1;
  467. }
  468.  
  469. int String::match(int start, int sl, int exact, const char* t, int tl) const
  470. {
  471.   if (tl < 0) tl = slen(t);
  472.  
  473.   if (start < 0)
  474.   {
  475.     start = sl + start - tl + 1;
  476.     if (start < 0 || (exact && start != 0))
  477.       return -1;
  478.   }
  479.   else if (exact && sl - start != tl)
  480.     return -1;
  481.  
  482.   if (sl == 0 || tl == 0 || sl - start < tl || start >= sl)
  483.     return -1;
  484.  
  485.   int n = tl;
  486.   const char* s = &(rep->s[start]);
  487.   while (--n >= 0) if (*s++ != *t++) return -1;
  488.   return tl;
  489. }
  490.  
  491. void SubString::assign(const StrRep* ysrc, const char* ys, int ylen)
  492. {
  493.   if (&S == &_nilString) return;
  494.  
  495.   if (ylen < 0) ylen = slen(ys);
  496.   StrRep* targ = S.rep;
  497.   int sl = targ->len - len + ylen;
  498.  
  499.   if (ysrc == targ || sl >= targ->sz)
  500.   {
  501.     StrRep* oldtarg = targ;
  502.     targ = Sresize(0, sl);
  503.     ncopy(oldtarg->s, targ->s, pos);
  504.     ncopy(ys, &(targ->s[pos]), ylen);
  505.     scopy(&(oldtarg->s[pos + len]), &(targ->s[pos + ylen]));
  506.     delete oldtarg;
  507.   }
  508.   else if (len == ylen)
  509.     ncopy(ys, &(targ->s[pos]), len);
  510.   else if (ylen < len)
  511.   {
  512.     ncopy(ys, &(targ->s[pos]), ylen);
  513.     scopy(&(targ->s[pos + len]), &(targ->s[pos + ylen]));
  514.   }
  515.   else
  516.   {
  517.     revcopy(&(targ->s[targ->len]), &(targ->s[sl]), targ->len-pos-len +1);
  518.     ncopy(ys, &(targ->s[pos]), ylen);
  519.   }
  520.   targ->len = sl;
  521.   S.rep = targ;
  522. }
  523.  
  524.  
  525.  
  526. /*
  527.  * substitution
  528.  */
  529.  
  530.  
  531. int String::_gsub(const char* pat, int pl, const char* r, int rl)
  532. {
  533.   int nmatches = 0;
  534.   if (pl < 0) pl = slen(pat);
  535.   if (rl < 0) rl = slen(r);
  536.   int sl = length();
  537.   if (sl <= 0 || pl <= 0 || sl < pl)
  538.     return nmatches;
  539.   
  540.   const char* s = chars();
  541.  
  542.   // prepare to make new rep
  543.   StrRep* nrep = 0;
  544.   int nsz = 0;
  545.   char* x = 0;
  546.  
  547.   int si = 0;
  548.   int xi = 0;
  549.   int remaining = sl;
  550.  
  551.   while (remaining >= pl)
  552.   {
  553.     int pos = search(si, sl, pat, pl);
  554.     if (pos < 0)
  555.       break;
  556.     else
  557.     {
  558.       ++nmatches;
  559.       int mustfit = xi + remaining + rl - pl;
  560.       if (mustfit >= nsz)
  561.       {
  562.         if (nrep != 0) nrep->len = xi;
  563.         nrep = Sresize(nrep, mustfit);
  564.         nsz = nrep->sz;
  565.         x = nrep->s;
  566.       }
  567.       pos -= si;
  568.       ncopy(&(s[si]), &(x[xi]), pos);
  569.       ncopy(r, &(x[xi + pos]), rl);
  570.       si += pos + pl;
  571.       remaining -= pos + pl;
  572.       xi += pos + rl;
  573.     }
  574.   }
  575.  
  576.   if (nrep == 0)
  577.   {
  578.     if (nmatches == 0)
  579.       return nmatches;
  580.     else
  581.       nrep = Sresize(nrep, xi+remaining);
  582.   }
  583.  
  584.   ncopy0(&(s[si]), &(x[xi]), remaining);
  585.   nrep->len = xi + remaining;
  586.  
  587.   if (nrep->len <= rep->sz)   // fit back in if possible
  588.   {
  589.     rep->len = nrep->len;
  590.     ncopy0(nrep->s, rep->s, rep->len);
  591.     delete(nrep);
  592.   }
  593.   else
  594.   {
  595.     delete(rep);
  596.     rep = nrep;
  597.   }
  598.   return nmatches;
  599. }
  600.  
  601. int String::_gsub(const Regex& pat, const char* r, int rl)
  602. {
  603.   int nmatches = 0;
  604.   int sl = length();
  605.   if (sl <= 0)
  606.     return nmatches;
  607.  
  608.   if (rl < 0) rl = slen(r);
  609.  
  610.   const char* s = chars();
  611.  
  612.   StrRep* nrep = 0;
  613.   int nsz = 0;
  614.  
  615.   char* x = 0;
  616.  
  617.   int si = 0;
  618.   int xi = 0;
  619.   int remaining = sl;
  620.   int  pos, pl = 0;                  // how long is a regular expression?
  621.  
  622.   while (remaining > 0)
  623.   {
  624.     pos = pat.search(s, sl, pl, si); // unlike string search, the pos returned here is absolute
  625.     if (pos < 0 || pl <= 0)
  626.       break;
  627.     else
  628.     {
  629.       ++nmatches;
  630.       int mustfit = xi + remaining + rl - pl;
  631.       if (mustfit >= nsz)
  632.       {
  633.         if (nrep != 0) nrep->len = xi;
  634.         nrep = Sresize(nrep, mustfit);
  635.         x = nrep->s;
  636.         nsz = nrep->sz;
  637.       }
  638.       pos -= si;
  639.       ncopy(&(s[si]), &(x[xi]), pos);
  640.       ncopy(r, &(x[xi + pos]), rl);
  641.       si += pos + pl;
  642.       remaining -= pos + pl;
  643.       xi += pos + rl;
  644.     }
  645.   }
  646.  
  647.   if (nrep == 0)
  648.   {
  649.     if (nmatches == 0)
  650.       return nmatches;
  651.     else
  652.       nrep = Sresize(nrep, xi+remaining);
  653.   }
  654.  
  655.   ncopy0(&(s[si]), &(x[xi]), remaining);
  656.   nrep->len = xi + remaining;
  657.  
  658.   if (nrep->len <= rep->sz)   // fit back in if possible
  659.   {
  660.     rep->len = nrep->len;
  661.     ncopy0(nrep->s, rep->s, rep->len);
  662.     delete(nrep);
  663.   }
  664.   else
  665.   {
  666.     delete(rep);
  667.     rep = nrep;
  668.   }
  669.   return nmatches;
  670. }
  671.  
  672.  
  673. /*
  674.  * deletion
  675.  */
  676.  
  677. void String::del(int pos, int len)
  678. {
  679.   if (pos < 0 || len <= 0 || (unsigned)(pos + len) > length()) return;
  680.   int nlen = length() - len;
  681.   int first = pos + len;
  682.   ncopy0(&(rep->s[first]), &(rep->s[pos]), length() - first);
  683.   rep->len = nlen;
  684. }
  685.  
  686. void String::del(const Regex& r, int startpos)
  687. {
  688.   int mlen;
  689.   int first = r.search(chars(), length(), mlen, startpos);
  690.   del(first, mlen);
  691. }
  692.  
  693. void String::del(const char* t, int startpos)
  694. {
  695.   int tlen = slen(t);
  696.   int p = search(startpos, length(), t, tlen);
  697.   del(p, tlen);
  698. }
  699.  
  700. void String::del(const String& y, int startpos)
  701. {
  702.   del(search(startpos, length(), y.chars(), y.length()), y.length());
  703. }
  704.  
  705. void String::del(const SubString& y, int startpos)
  706. {
  707.   del(search(startpos, length(), y.chars(), y.length()), y.length());
  708. }
  709.  
  710. void String::del(char c, int startpos)
  711. {
  712.   del(search(startpos, length(), c), 1);
  713. }
  714.  
  715. /*
  716.  * substring extraction
  717.  */
  718.  
  719.  
  720. SubString String::at(int first, int len)
  721. {
  722.   return _substr(first, len);
  723. }
  724.  
  725. SubString String::operator() (int first, int len)
  726. {
  727.   return _substr(first, len);
  728. }
  729.  
  730. SubString String::before(int pos)
  731. {
  732.   return _substr(0, pos);
  733. }
  734.  
  735. SubString String::through(int pos)
  736. {
  737.   return _substr(0, pos+1);
  738. }
  739.  
  740. SubString String::after(int pos)
  741. {
  742.   return _substr(pos + 1, length() - (pos + 1));
  743. }
  744.  
  745. SubString String::from(int pos)
  746. {
  747.   return _substr(pos, length() - pos);
  748. }
  749.  
  750. SubString String::at(const String& y, int startpos)
  751. {
  752.   int first = search(startpos, length(), y.chars(), y.length());
  753.   return _substr(first,  y.length());
  754. }
  755.  
  756. SubString String::at(const SubString& y, int startpos)
  757. {
  758.   int first = search(startpos, length(), y.chars(), y.length());
  759.   return _substr(first, y.length());
  760. }
  761.  
  762. SubString String::at(const Regex& r, int startpos)
  763. {
  764.   int mlen;
  765.   int first = r.search(chars(), length(), mlen, startpos);
  766.   return _substr(first, mlen);
  767. }
  768.  
  769. SubString String::at(const char* t, int startpos)
  770. {
  771.   int tlen = slen(t);
  772.   int first = search(startpos, length(), t, tlen);
  773.   return _substr(first, tlen);
  774. }
  775.  
  776. SubString String::at(char c, int startpos)
  777. {
  778.   int first = search(startpos, length(), c);
  779.   return _substr(first, 1);
  780. }
  781.  
  782. SubString String::before(const String& y, int startpos)
  783. {
  784.   int last = search(startpos, length(), y.chars(), y.length());
  785.   return _substr(0, last);
  786. }
  787.  
  788. SubString String::before(const SubString& y, int startpos)
  789. {
  790.   int last = search(startpos, length(), y.chars(), y.length());
  791.   return _substr(0, last);
  792. }
  793.  
  794. SubString String::before(const Regex& r, int startpos)
  795. {
  796.   int mlen;
  797.   int first = r.search(chars(), length(), mlen, startpos);
  798.   return _substr(0, first);
  799. }
  800.  
  801. SubString String::before(char c, int startpos)
  802. {
  803.   int last = search(startpos, length(), c);
  804.   return _substr(0, last);
  805. }
  806.  
  807. SubString String::before(const char* t, int startpos)
  808. {
  809.   int tlen = slen(t);
  810.   int last = search(startpos, length(), t, tlen);
  811.   return _substr(0, last);
  812. }
  813.  
  814. SubString String::through(const String& y, int startpos)
  815. {
  816.   int last = search(startpos, length(), y.chars(), y.length());
  817.   if (last >= 0) last += y.length();
  818.   return _substr(0, last);
  819. }
  820.  
  821. SubString String::through(const SubString& y, int startpos)
  822. {
  823.   int last = search(startpos, length(), y.chars(), y.length());
  824.   if (last >= 0) last += y.length();
  825.   return _substr(0, last);
  826. }
  827.  
  828. SubString String::through(const Regex& r, int startpos)
  829. {
  830.   int mlen;
  831.   int first = r.search(chars(), length(), mlen, startpos);
  832.   if (first >= 0) first += mlen;
  833.   return _substr(0, first);
  834. }
  835.  
  836. SubString String::through(char c, int startpos)
  837. {
  838.   int last = search(startpos, length(), c);
  839.   if (last >= 0) last += 1;
  840.   return _substr(0, last);
  841. }
  842.  
  843. SubString String::through(const char* t, int startpos)
  844. {
  845.   int tlen = slen(t);
  846.   int last = search(startpos, length(), t, tlen);
  847.   if (last >= 0) last += tlen;
  848.   return _substr(0, last);
  849. }
  850.  
  851. SubString String::after(const String& y, int startpos)
  852. {
  853.   int first = search(startpos, length(), y.chars(), y.length());
  854.   if (first >= 0) first += y.length();
  855.   return _substr(first, length() - first);
  856. }
  857.  
  858. SubString String::after(const SubString& y, int startpos)
  859. {
  860.   int first = search(startpos, length(), y.chars(), y.length());
  861.   if (first >= 0) first += y.length();
  862.   return _substr(first, length() - first);
  863. }
  864.  
  865. SubString String::after(char c, int startpos)
  866. {
  867.   int first = search(startpos, length(), c);
  868.   if (first >= 0) first += 1;
  869.   return _substr(first, length() - first);
  870. }
  871.  
  872. SubString String::after(const Regex& r, int startpos)
  873. {
  874.   int mlen;
  875.   int first = r.search(chars(), length(), mlen, startpos);
  876.   if (first >= 0) first += mlen;
  877.   return _substr(first, length() - first);
  878. }
  879.  
  880. SubString String::after(const char* t, int startpos)
  881. {
  882.   int tlen = slen(t);
  883.   int first = search(startpos, length(), t, tlen);
  884.   if (first >= 0) first += tlen;
  885.   return _substr(first, length() - first);
  886. }
  887.  
  888. SubString String::from(const String& y, int startpos)
  889. {
  890.   int first = search(startpos, length(), y.chars(), y.length());
  891.   return _substr(first, length() - first);
  892. }
  893.  
  894. SubString String::from(const SubString& y, int startpos)
  895. {
  896.   int first = search(startpos, length(), y.chars(), y.length());
  897.   return _substr(first, length() - first);
  898. }
  899.  
  900. SubString String::from(const Regex& r, int startpos)
  901. {
  902.   int mlen;
  903.   int first = r.search(chars(), length(), mlen, startpos);
  904.   return _substr(first, length() - first);
  905. }
  906.  
  907. SubString String::from(char c, int startpos)
  908. {
  909.   int first = search(startpos, length(), c);
  910.   return _substr(first, length() - first);
  911. }
  912.  
  913. SubString String::from(const char* t, int startpos)
  914. {
  915.   int tlen = slen(t);
  916.   int first = search(startpos, length(), t, tlen);
  917.   return _substr(first, length() - first);
  918. }
  919.  
  920.  
  921.  
  922. /*
  923.  * split/join
  924.  */
  925.  
  926.  
  927. int split(const String& src, String results[], int n, const String& sep)
  928. {
  929.   String x = src;
  930.   const char* s = x.chars();
  931.   int sl = x.length();
  932.   int i = 0;
  933.   int pos = 0;
  934.   while (i < n && pos < sl)
  935.   {
  936.     int p = x.search(pos, sl, sep.chars(), sep.length());
  937.     if (p < 0)
  938.       p = sl;
  939.     results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  940.     i++;
  941.     pos = p + sep.length();
  942.   }
  943.   return i;
  944. }
  945.  
  946. int split(const String& src, String results[], int n, const Regex& r)
  947. {
  948.   String x = src;
  949.   const char* s = x.chars();
  950.   int sl = x.length();
  951.   int i = 0;
  952.   int pos = 0;
  953.   int p, matchlen;
  954.   while (i < n && pos < sl)
  955.   {
  956.     p = r.search(s, sl, matchlen, pos);
  957.     if (p < 0)
  958.       p = sl;
  959.     results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  960.     i++;
  961.     pos = p + matchlen;
  962.   }
  963.   return i;
  964. }
  965.  
  966.  
  967. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  968. #define RETURN(r) return
  969. #define RETURNS(r) return r;
  970. #define RETURN_OBJECT(TYPE, NAME) /* nothing */
  971. #else /* _G_NO_NRV */
  972. #define RETURN(r) return r
  973. #define RETURNS(r) /* nothing */
  974. #define RETURN_OBJECT(TYPE, NAME) TYPE NAME;
  975. #endif
  976.  
  977. String join(String src[], int n, const String& separator) RETURNS(x)
  978. {
  979.   RETURN_OBJECT(String,x)
  980.   String sep = separator;
  981.   int xlen = 0;
  982.   for (int i = 0; i < n; ++i)
  983.     xlen += src[i].length();
  984.   xlen += (n - 1) * sep.length();
  985.  
  986.   x.rep = Sresize (x.rep, xlen);
  987.  
  988.   int j = 0;
  989.   
  990.   for (i = 0; i < n - 1; ++i)
  991.   {
  992.     ncopy(src[i].chars(), &(x.rep->s[j]), src[i].length());
  993.     j += src[i].length();
  994.     ncopy(sep.chars(), &(x.rep->s[j]), sep.length());
  995.     j += sep.length();
  996.   }
  997.   ncopy0(src[i].chars(), &(x.rep->s[j]), src[i].length());
  998.   RETURN(x);
  999. }
  1000.   
  1001. /*
  1002.  misc
  1003. */
  1004.  
  1005.     
  1006. StrRep* Sreverse(const StrRep* src, StrRep* dest)
  1007. {
  1008.   int n = src->len;
  1009.   if (src != dest)
  1010.     dest = Salloc(dest, src->s, n, n);
  1011.   if (n > 0)
  1012.   {
  1013.     char* a = dest->s;
  1014.     char* b = &(a[n - 1]);
  1015.     while (a < b)
  1016.     {
  1017.       char t = *a;
  1018.       *a++ = *b;
  1019.       *b-- = t;
  1020.     }
  1021.   }
  1022.   return dest;
  1023. }
  1024.  
  1025.  
  1026. StrRep* Supcase(const StrRep* src, StrRep* dest)
  1027. {
  1028.   int n = src->len;
  1029.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  1030.   char* p = dest->s;
  1031.   char* e = &(p[n]);
  1032.   for (; p < e; ++p) if (islower(*p)) *p = toupper(*p);
  1033.   return dest;
  1034. }
  1035.  
  1036. StrRep* Sdowncase(const StrRep* src, StrRep* dest)
  1037. {
  1038.   int n = src->len;
  1039.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  1040.   char* p = dest->s;
  1041.   char* e = &(p[n]);
  1042.   for (; p < e; ++p) if (isupper(*p)) *p = tolower(*p);
  1043.   return dest;
  1044. }
  1045.  
  1046. StrRep* Scapitalize(const StrRep* src, StrRep* dest)
  1047. {
  1048.   int n = src->len;
  1049.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  1050.  
  1051.   char* p = dest->s;
  1052.   char* e = &(p[n]);
  1053.   for (; p < e; ++p)
  1054.   {
  1055.     int at_word;
  1056.     if (at_word = islower(*p))
  1057.       *p = toupper(*p);
  1058.     else 
  1059.       at_word = isupper(*p) || isdigit(*p);
  1060.  
  1061.     if (at_word)
  1062.     {
  1063.       while (++p < e)
  1064.       {
  1065.         if (isupper(*p))
  1066.           *p = tolower(*p);
  1067.     /* A '\'' does not break a word, so that "Nathan's" stays
  1068.        "Nathan's" rather than turning into "Nathan'S". */
  1069.         else if (!islower(*p) && !isdigit(*p) && (*p != '\''))
  1070.           break;
  1071.       }
  1072.     }
  1073.   }
  1074.   return dest;
  1075. }
  1076.  
  1077. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  1078.  
  1079. String replicate(char c, int n) return w;
  1080. {
  1081.   w.rep = Sresize(w.rep, n);
  1082.   char* p = w.rep->s;
  1083.   while (n-- > 0) *p++ = c;
  1084.   *p = 0;
  1085. }
  1086.  
  1087. String replicate(const String& y, int n) return w
  1088. {
  1089.   int len = y.length();
  1090.   w.rep = Sresize(w.rep, n * len);
  1091.   char* p = w.rep->s;
  1092.   while (n-- > 0)
  1093.   {
  1094.     ncopy(y.chars(), p, len);
  1095.     p += len;
  1096.   }
  1097.   *p = 0;
  1098. }
  1099.  
  1100. String common_prefix(const String& x, const String& y, int startpos) return r;
  1101. {
  1102.   const char* xchars = x.chars();
  1103.   const char* ychars = y.chars();
  1104.   const char* xs = &(xchars[startpos]);
  1105.   const char* ss = xs;
  1106.   const char* topx = &(xchars[x.length()]);
  1107.   const char* ys = &(ychars[startpos]);
  1108.   const char* topy = &(ychars[y.length()]);
  1109.   for (int l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
  1110.   r.rep = Salloc(r.rep, ss, l, l);
  1111. }
  1112.  
  1113. String common_suffix(const String& x, const String& y, int startpos) return r;
  1114. {
  1115.   const char* xchars = x.chars();
  1116.   const char* ychars = y.chars();
  1117.   const char* xs = &(xchars[x.length() + startpos]);
  1118.   const char* botx = xchars;
  1119.   const char* ys = &(ychars[y.length() + startpos]);
  1120.   const char* boty = ychars;
  1121.   for (int l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
  1122.   r.rep = Salloc(r.rep, ++xs, l, l);
  1123. }
  1124.  
  1125. #else
  1126.  
  1127. String replicate(char c, int n)
  1128. {
  1129.   String w;
  1130.   w.rep = Sresize(w.rep, n);
  1131.   char* p = w.rep->s;
  1132.   while (n-- > 0) *p++ = c;
  1133.   *p = 0;
  1134.   return w;
  1135. }
  1136.  
  1137. String replicate(const String& y, int n)
  1138. {
  1139.   String w;
  1140.   int len = y.length();
  1141.   w.rep = Sresize(w.rep, n * len);
  1142.   char* p = w.rep->s;
  1143.   while (n-- > 0)
  1144.   {
  1145.     ncopy(y.chars(), p, len);
  1146.     p += len;
  1147.   }
  1148.   *p = 0;
  1149.   return w;
  1150. }
  1151.  
  1152. String common_prefix(const String& x, const String& y, int startpos)
  1153. {
  1154.   String r;
  1155.   const char* xchars = x.chars();
  1156.   const char* ychars = y.chars();
  1157.   const char* xs = &(xchars[startpos]);
  1158.   const char* ss = xs;
  1159.   const char* topx = &(xchars[x.length()]);
  1160.   const char* ys = &(ychars[startpos]);
  1161.   const char* topy = &(ychars[y.length()]);
  1162.   for (int l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
  1163.   r.rep = Salloc(r.rep, ss, l, l);
  1164.   return r;
  1165. }
  1166.  
  1167. String common_suffix(const String& x, const String& y, int startpos) 
  1168. {
  1169.   String r;
  1170.   const char* xchars = x.chars();
  1171.   const char* ychars = y.chars();
  1172.   const char* xs = &(xchars[x.length() + startpos]);
  1173.   const char* botx = xchars;
  1174.   const char* ys = &(ychars[y.length() + startpos]);
  1175.   const char* boty = ychars;
  1176.   for (int l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
  1177.   r.rep = Salloc(r.rep, ++xs, l, l);
  1178.   return r;
  1179. }
  1180.  
  1181. #endif
  1182.  
  1183. // IO
  1184.  
  1185. istream& operator>>(istream& s, String& x)
  1186. {
  1187.   if (!s.ipfx(0) || (!(s.flags() & ios::skipws) && !ws(s)))
  1188.   {
  1189.     s.clear(ios::failbit|s.rdstate()); // Redundant if using GNU iostreams.
  1190.     return s;
  1191.   }
  1192.   int ch;
  1193.   int i = 0;
  1194.   x.rep = Sresize(x.rep, 20);
  1195.   register streambuf *sb = s.rdbuf();
  1196.   while ((ch = sb->sbumpc()) != EOF)
  1197.   {
  1198.     if (isspace(ch))
  1199.       break;
  1200.     if (i >= x.rep->sz - 1)
  1201.       x.rep = Sresize(x.rep, i+1);
  1202.     x.rep->s[i++] = ch;
  1203.   }
  1204.   x.rep->s[i] = 0;
  1205.   x.rep->len = i;
  1206.   int new_state = s.rdstate();
  1207.   if (i == 0) new_state |= ios::failbit;
  1208.   if (ch == EOF) new_state |= ios::eofbit;
  1209.   s.clear(new_state);
  1210.   return s;
  1211. }
  1212.  
  1213. int readline(istream& s, String& x, char terminator, int discard)
  1214. {
  1215.   if (!s.ipfx(0))
  1216.     return 0;
  1217.   int ch;
  1218.   int i = 0;
  1219.   x.rep = Sresize(x.rep, 80);
  1220.   register streambuf *sb = s.rdbuf();
  1221.   while ((ch = sb->sbumpc()) != EOF)
  1222.   {
  1223.     if (ch != terminator || !discard)
  1224.     {
  1225.       if (i >= x.rep->sz - 1)
  1226.         x.rep = Sresize(x.rep, i+1);
  1227.       x.rep->s[i++] = ch;
  1228.     }
  1229.     if (ch == terminator)
  1230.       break;
  1231.   }
  1232.   x.rep->s[i] = 0;
  1233.   x.rep->len = i;
  1234.   if (ch == EOF) s.clear(ios::eofbit|s.rdstate());
  1235.   return i;
  1236. }
  1237.  
  1238.  
  1239. ostream& operator<<(ostream& s, const SubString& x)
  1240. { 
  1241.   const char* a = x.chars();
  1242.   const char* lasta = &(a[x.length()]);
  1243.   while (a < lasta)
  1244.     s.put(*a++);
  1245.   return(s);
  1246. }
  1247.  
  1248. // from John.Willis@FAS.RI.CMU.EDU
  1249.  
  1250. int String::freq(const SubString& y) const
  1251. {
  1252.   int found = 0;
  1253.   for (unsigned int i = 0; i < length(); i++) 
  1254.     if (match(i,length(),0,y.chars(), y.length())>= 0) found++;
  1255.   return(found);
  1256. }
  1257.  
  1258. int String::freq(const String& y) const
  1259. {
  1260.   int found = 0;
  1261.   for (unsigned int i = 0; i < length(); i++) 
  1262.     if (match(i,length(),0,y.chars(),y.length()) >= 0) found++;
  1263.   return(found);
  1264. }
  1265.  
  1266. int String::freq(const char* t) const
  1267. {
  1268.   int found = 0;
  1269.   for (unsigned int i = 0; i < length(); i++) 
  1270.     if (match(i,length(),0,t) >= 0) found++;
  1271.   return(found);
  1272. }
  1273.  
  1274. int String::freq(char c) const
  1275. {
  1276.   int found = 0;
  1277.   for (unsigned int i = 0; i < length(); i++) 
  1278.     if (match(i,length(),0,&c,1) >= 0) found++;
  1279.   return(found);
  1280. }
  1281.  
  1282.  
  1283. int String::OK() const
  1284. {
  1285.   if (rep == 0             // don't have a rep
  1286.     || rep->len > rep->sz     // string oustide bounds
  1287.     || rep->s[rep->len] != 0)   // not null-terminated
  1288.       error("invariant failure");
  1289.   return 1;
  1290. }
  1291.  
  1292. int SubString::OK() const
  1293. {
  1294.   int v = S != (const char*)0; // have a String;
  1295.   v &= S.OK();                 // that is legal
  1296.   v &= pos + len >= S.rep->len;// pos and len within bounds
  1297.   if (!v) S.error("SubString invariant failure");
  1298.   return v;
  1299. }
  1300.  
  1301.